package algo.A00_前置基础;

/**
 * 最大公约数：辗转相除法(欧几里得算法)
 * 如果m%n==0，则gcd(m,n)是n
 * 否则，gcd(m,n)是gcd(n,m%n)
 * 一次取余数后，m变成n，n变成m%n
 */
public class M02_最大公约数 {
    public static void main(String[] args) {
        int m = 54;
        int n = 96;
        int gcd = gcd(m, n);
        System.out.println("gcd = " + gcd);
    }

    public static int gcd(int m, int n) {
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }
        while (m % n != 0) {
            int temp = n;
            n = m % n;
            m = temp;
        }
        return n;
    }
}
